Finding Missing Patterns
Identifieur interne : 003158 ( Main/Exploration ); précédent : 003157; suivant : 003159Finding Missing Patterns
Auteurs : Shunsuke Inenaga [Finlande] ; Teemu Kivioja [Finlande] ; Veli M Kinen [Finlande]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: Consider the following problem: Find the shortest pattern that does not occur in a given text. To make the problem non-trivial, the pattern is required to consist only of characters that occur in the text. This problem can be solved easily in linear time using the suffix tree of the text. In this paper, we study an extension of this problem, namely the missing patterns problem: Find the shortest pair of patterns that do not occur close to each other in a given text, i.e., the distance between their occurrences is always greater than a given threshold α. We show that the missing patterns problem can be solved in O( min (αnlogn,n 2)) time, where n is the size of the text. For the special case where both pairs are required to have the same length, we give an algorithm with time complexity O(αn log log n). The problem is motivated by optimization of multiplexed nested-PCR.
Url:
DOI: 10.1007/978-3-540-30219-3_39
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000C39
- to stream Istex, to step Curation: 000C39
- to stream Istex, to step Checkpoint: 000C16
- to stream Main, to step Merge: 003190
- to stream Main, to step Curation: 003158
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Finding Missing Patterns</title><author><name sortKey="Inenaga, Shunsuke" sort="Inenaga, Shunsuke" uniqKey="Inenaga S" first="Shunsuke" last="Inenaga">Shunsuke Inenaga</name></author><author><name sortKey="Kivioja, Teemu" sort="Kivioja, Teemu" uniqKey="Kivioja T" first="Teemu" last="Kivioja">Teemu Kivioja</name></author><author><name sortKey="M Kinen, Veli" sort="M Kinen, Veli" uniqKey="M Kinen V" first="Veli" last="M Kinen">Veli M Kinen</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:6466751D0FA88BC66E245D7C0C208E0CE4FFACC9</idno><date when="2004" year="2004">2004</date><idno type="doi">10.1007/978-3-540-30219-3_39</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-JSPK9HT9-G/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">000C39</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000C39</idno><idno type="wicri:Area/Istex/Curation">000C39</idno><idno type="wicri:Area/Istex/Checkpoint">000C16</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000C16</idno><idno type="wicri:doubleKey">0302-9743:2004:Inenaga S:finding:missing:patterns</idno><idno type="wicri:Area/Main/Merge">003190</idno><idno type="wicri:Area/Main/Curation">003158</idno><idno type="wicri:Area/Main/Exploration">003158</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Finding Missing Patterns</title><author><name sortKey="Inenaga, Shunsuke" sort="Inenaga, Shunsuke" uniqKey="Inenaga S" first="Shunsuke" last="Inenaga">Shunsuke Inenaga</name><affiliation wicri:level="4"><country xml:lang="fr">Finlande</country><wicri:regionArea>Department of Computer Science, University of Helsinki, (Teollisuuskatu 23), P.O. Box 26, FIN-00014</wicri:regionArea><orgName type="university">Université d'Helsinki</orgName><placeName><settlement type="city">Helsinki</settlement><region type="région" nuts="2">Uusimaa</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Finlande</country></affiliation></author><author><name sortKey="Kivioja, Teemu" sort="Kivioja, Teemu" uniqKey="Kivioja T" first="Teemu" last="Kivioja">Teemu Kivioja</name><affiliation wicri:level="4"><country xml:lang="fr">Finlande</country><wicri:regionArea>Department of Computer Science, University of Helsinki, (Teollisuuskatu 23), P.O. Box 26, FIN-00014</wicri:regionArea><orgName type="university">Université d'Helsinki</orgName><placeName><settlement type="city">Helsinki</settlement><region type="région" nuts="2">Uusimaa</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Finlande</country></affiliation></author><author><name sortKey="M Kinen, Veli" sort="M Kinen, Veli" uniqKey="M Kinen V" first="Veli" last="M Kinen">Veli M Kinen</name><affiliation wicri:level="4"><country xml:lang="fr">Finlande</country><wicri:regionArea>Department of Computer Science, University of Helsinki, (Teollisuuskatu 23), P.O. Box 26, FIN-00014</wicri:regionArea><orgName type="university">Université d'Helsinki</orgName><placeName><settlement type="city">Helsinki</settlement><region type="région" nuts="2">Uusimaa</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Finlande</country></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Consider the following problem: Find the shortest pattern that does not occur in a given text. To make the problem non-trivial, the pattern is required to consist only of characters that occur in the text. This problem can be solved easily in linear time using the suffix tree of the text. In this paper, we study an extension of this problem, namely the missing patterns problem: Find the shortest pair of patterns that do not occur close to each other in a given text, i.e., the distance between their occurrences is always greater than a given threshold α. We show that the missing patterns problem can be solved in O( min (αnlogn,n 2)) time, where n is the size of the text. For the special case where both pairs are required to have the same length, we give an algorithm with time complexity O(αn log log n). The problem is motivated by optimization of multiplexed nested-PCR.</div></front></TEI><affiliations><list><country><li>Finlande</li></country><region><li>Uusimaa</li></region><settlement><li>Helsinki</li></settlement><orgName><li>Université d'Helsinki</li></orgName></list><tree><country name="Finlande"><region name="Uusimaa"><name sortKey="Inenaga, Shunsuke" sort="Inenaga, Shunsuke" uniqKey="Inenaga S" first="Shunsuke" last="Inenaga">Shunsuke Inenaga</name></region><name sortKey="Inenaga, Shunsuke" sort="Inenaga, Shunsuke" uniqKey="Inenaga S" first="Shunsuke" last="Inenaga">Shunsuke Inenaga</name><name sortKey="Kivioja, Teemu" sort="Kivioja, Teemu" uniqKey="Kivioja T" first="Teemu" last="Kivioja">Teemu Kivioja</name><name sortKey="Kivioja, Teemu" sort="Kivioja, Teemu" uniqKey="Kivioja T" first="Teemu" last="Kivioja">Teemu Kivioja</name><name sortKey="M Kinen, Veli" sort="M Kinen, Veli" uniqKey="M Kinen V" first="Veli" last="M Kinen">Veli M Kinen</name><name sortKey="M Kinen, Veli" sort="M Kinen, Veli" uniqKey="M Kinen V" first="Veli" last="M Kinen">Veli M Kinen</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003158 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 003158 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Sante
|area= MersV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:6466751D0FA88BC66E245D7C0C208E0CE4FFACC9
|texte= Finding Missing Patterns
}}
| This area was generated with Dilib version V0.6.33. |  |